SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Apex graph</title>

</head>

Apex graph

</h1>

</header>

In <a href="Graph_theory" title="Graph theory">graph theory</a>, a branch of mathematics, an apex graph is a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> that can be made <a href="Planar_graph" title="Planar graph">planar</a> by the removal of a single <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertex</a>. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The <a href="Null_graph" title="Null graph">null graph</a> is also counted as an apex graph even though it has no vertex to remove.

Apex graphs are <a href="Closure_(mathematics)" title="Closure (mathematics)">closed</a> under the operation of taking <a href="Graph_minor" title="Graph minor">minors</a> and play a role in several other aspects of graph minor theory: <a href="Linkless_embedding" title="Linkless embedding">linkless embedding</a>,<a href="#cite_note-linkless-1">[1]</a> <a href="Hadwiger_conjecture_(graph_theory)" title="Hadwiger conjecture (graph theory)">Hadwiger's conjecture</a>,<a href="#cite_note-rst93-2">[2]</a> YΔY-reducible graphs,<a href="#cite_note-t92-3">[3]</a> and relations between <a href="Treewidth" title="Treewidth">treewidth</a> and <a href="Diameter_(graph_theory)" title="Diameter (graph theory)">graph diameter</a>.<a href="#cite_note-local-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Characterization_and_recognition">Characterization and recognition</h2></div>

Apex graphs are <a href="Closure_(mathematics)" title="Closure (mathematics)">closed</a> under the operation of taking <a href="Graph_minor" title="Graph minor">minors</a>: contracting any edge, or removing any edge or vertex, leads to another apex graph. For, if G is an apex graph with apex v, then any contraction or removal that does not involve v preserves the planarity of the remaining graph, as does any edge removal of an edge incident to v. If an edge incident to v is contracted, the effect on the remaining graph is equivalent to the removal of the other endpoint of the edge. And if v itself is removed, any other vertex may be chosen as the apex.<a href="#cite_note-gi91-5">[5]</a>

By the <a href="Robertson%E2%80%93Seymour_theorem" title="Robertson–Seymour theorem">Robertson–Seymour theorem</a>, because they form a minor-closed family of graphs, the apex graphs have a <a href="Forbidden_graph_characterization" title="Forbidden graph characterization">forbidden graph characterization</a>.

There are only finitely many graphs that are neither apex graphs nor have another non-apex graph as a minor.

These graphs are forbidden minors for the property of being an apex graph.

Any other graph G is an apex graph if and only if none of the forbidden minors is a minor of G.

These forbidden minors include the seven graphs of the <a href="Petersen_family" title="Petersen family">Petersen family</a>, three disconnected graphs formed from the disjoint unions of two of K5 and K3,3, and many other graphs. However, a complete description of them remains unknown.<a href="#cite_note-gi91-5">[5]</a><a href="#cite_note-FOOTNOTEPierce2014-6">[6]</a>

Despite the complete set of forbidden minors remaining unknown, it is possible to test whether a given graph is an apex graph, and if so, to find an apex for the graph, in <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a>. More generally, for any fixed constant k, it is possible to recognize in linear time the k-apex graphs, the graphs in which the removal of some carefully chosen set of at most k vertices leads to a planar graph.<a href="#cite_note-7">[7]</a> If k is variable, however, the problem is <a href="NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a>.<a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Chromatic_number">Chromatic number</h2></div>

Every apex graph has <a href="Graph_coloring" title="Graph coloring">chromatic number</a> at most five: the underlying planar graph requires at most four colors by the <a href="Four_color_theorem" title="Four color theorem">four color theorem</a>, and the remaining vertex needs at most one additional color. <a href="#CITEREFRobertsonSeymourThomas1993a">Robertson, Seymour & Thomas (1993a)</a> used this fact in their proof of the case k = 6 of the <a href="Hadwiger_conjecture_(graph_theory)" title="Hadwiger conjecture (graph theory)">Hadwiger conjecture</a>, the statement that every 6-chromatic graph has the <a href="Complete_graph" title="Complete graph">complete graph</a> K6 as a minor: they showed that any minimal counterexample to the conjecture would have to be an apex graph, but since there are no 6-chromatic apex graphs such a counterexample cannot exist.

/* start https://en.wikipedia.org/ */

.mw-parser-output .unsolved{margin:0.5em 0 1em 1em;border:1px solid #a2a9b1;padding:0.35em 0.35em 0.35em 2.2em;background-color:var(--background-color-interactive-subtle);background-image:url("./mw/Question%2C_Web_Fundamentals.svg");background-position:top 50%left 0.35em;background-size:1.5em;background-repeat:no-repeat}@media(min-width:720px){.mw-parser-output .unsolved{clear:right;float:right;max-width:25%}}.mw-parser-output .unsolved-label{font-weight:bold}.mw-parser-output .unsolved-body{margin:0.35em;font-style:italic}.mw-parser-output .unsolved-more{font-size:smaller}

/* end https://en.wikipedia.org/ */

</style>

<div>Unsolved problem in mathematics</div>

<div class="unsolved-body">Is every 6-vertex-connected K6-minor-free graph an apex graph?</div>

<div class="unsolved-more"><a href="List_of_unsolved_problems_in_mathematics" title="List of unsolved problems in mathematics">More unsolved problems in mathematics</a></div>

</div>

<a href="#CITEREFJørgensen1994">Jørgensen (1994)</a> conjectured that every <a href="K-vertex-connected_graph" title="K-vertex-connected graph">6-vertex-connected</a> graph that does not have K6 as a minor must be an apex graph. If this were proved, the Robertson–Seymour–Thomas result on the Hadwiger conjecture would be an immediate consequence.<a href="#cite_note-rst93-2">[2]</a> Jørgensen's conjecture remains unproven.<a href="#cite_note-9">[9]</a> However, if false, it has only finitely many counterexamples.<a href="#cite_note-FOOTNOTEKawarabayashiNorineThomasWollan2012-10">[10]</a>

<div class="mw-heading mw-heading2"><h2 id="Local_treewidth">Local treewidth</h2></div>

A graph family F has bounded local treewidth if the graphs in F obey a functional relationship between <a href="Distance_(graph_theory)" title="Distance (graph theory)">diameter</a> and <a href="Treewidth" title="Treewidth">treewidth</a>: there exists a function f such that the treewidth of a diameter-d graph in F is at most f (d). The apex graphs do not have bounded local treewidth: the apex graphs formed by connecting an apex vertex to every vertex of an n × n <a href="Grid_graph" class="mw-redirect" title="Grid graph">grid graph</a> have treewidth n and diameter 2, so the treewidth is not bounded by a function of diameter for these graphs. However, apex graphs are intimately connected to bounded local treewidth: the minor-closed graph families F that have bounded local treewidth are exactly the families that have an apex graph as one of their forbidden minors.<a href="#cite_note-local-4">[4]</a> A minor-closed family of graphs that has an apex graph as one of its forbidden minors is known as apex-minor-free. With this terminology, the connection between apex graphs and local treewidth can be restated as the fact that apex-minor-free graph families are the same as minor-closed graph families with bounded local treewidth.

The concept of bounded local treewidth forms the basis of the theory of <a href="Bidimensionality" title="Bidimensionality">bidimensionality</a>, and allows for many algorithmic problems on apex-minor-free graphs to be solved exactly by a polynomial-time algorithm or a <a href="Fixed-parameter_tractability" class="mw-redirect" title="Fixed-parameter tractability">fixed-parameter tractable</a> algorithm, or approximated using a <a href="Polynomial-time_approximation_scheme" title="Polynomial-time approximation scheme">polynomial-time approximation scheme</a>.<a href="#cite_note-11">[11]</a> Apex-minor-free graph families obey a strengthened version of the <a href="Graph_structure_theorem" title="Graph structure theorem">graph structure theorem</a>, leading to additional approximation algorithms for <a href="Graph_coloring" title="Graph coloring">graph coloring</a> and the <a href="Travelling_salesman_problem" title="Travelling salesman problem">travelling salesman problem</a>.<a href="#cite_note-12">[12]</a> However, some of these results can also be extended to arbitrary minor-closed graph families via structure theorems relating them to apex-minor-free graphs.<a href="#cite_note-13">[13]</a>

<div class="mw-heading mw-heading2"><h2 id="Embeddings">Embeddings</h2></div>

If G is an apex graph with apex v, and τ is the minimum number of faces needed to cover all the neighbors of v in a planar embedding of G \ {v}, then G may be embedded onto a two-dimensional surface of <a href="Genus_(mathematics)" title="Genus (mathematics)">genus</a> τ – 1: simply add that number of bridges to the planar embedding, connecting together all the faces into which v must be connected. For instance, adding a single vertex to an <a href="Outerplanar_graph" title="Outerplanar graph">outerplanar graph</a> (a graph with τ = 1) produces a planar graph. When G \ {v} is 3-connected, his bound is within a constant factor of optimal: every surface embedding of G requires genus at least <style data-mw-deduplicate="TemplateStyles:r1214402035">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}

/* end https://en.wikipedia.org/ */

</style>⁠τ/160⁠. However, it is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a> to determine the optimal genus of a surface embedding of an apex graph.<a href="#cite_note-14">[14]</a>

By using <a href="SPQR_tree" title="SPQR tree">SPQR trees</a> to encode the possible embeddings of the planar part of an apex graph, it is possible to compute a <a href="Graph_drawing" title="Graph drawing">drawing</a> of the graph in the plane in which the only crossings involve the apex vertex, minimizing the total number of crossings, in polynomial time.<a href="#cite_note-15">[15]</a> However, if arbitrary crossings are allowed, it becomes NP-hard to minimize the number of crossings, even in the special case of apex graphs formed by adding a single edge to a planar graph.<a href="#cite_note-16">[16]</a>

Apex graphs are also <a href="Linkless_embedding" title="Linkless embedding">linklessly embeddable</a> in three-dimensional space: they can be embedded in such a way that each cycle in the graph is the boundary of a disk that is not crossed by any other feature of the graph.<a href="#cite_note-17">[17]</a> A drawing of this type may be obtained by drawing the planar part of the graph in a plane, placing the apex above the plane, and connecting the apex by straight-line edges to each of its neighbors. Linklessly embeddable graphs form a minor-closed family with the seven graphs in the <a href="Petersen_family" title="Petersen family">Petersen family</a> as their minimal forbidden minors;<a href="#cite_note-linkless-1">[1]</a> therefore, these graphs are also forbidden as minors for the apex graphs. However, there exist linklessly embeddable graphs that are not apex graphs.

<div class="mw-heading mw-heading2"><h2 id="YΔY-reducibility">YΔY-reducibility</h2></div>

A connected graph is YΔY-reducible if it can be reduced to a single vertex by a sequence of steps, each of which is a <a href="Y-%CE%94_transform" title="Y-Δ transform">Δ-Y or Y-Δ transform</a>, the removal of a self-loop or multiple adjacency, the removal of a vertex with one neighbor, and the replacement of a vertex of degree two and its two neighboring edges by a single edge.<a href="#cite_note-t92-3">[3]</a>

Like the apex graphs and the linkless embeddable graphs, the YΔY-reducible graphs are closed under graph minors. And, like the linkless embeddable graphs, the YΔY-reducible graphs have the seven graphs in the <a href="Petersen_family" title="Petersen family">Petersen family</a> as forbidden minors, prompting the question of whether these are the only forbidden minors and whether the YΔY-reducible graphs are the same as the linkless embeddable graphs. However, Neil Robertson provided an example of an apex graph that is not YΔY-reducible. Since every apex graph is linkless embeddable, this shows that there are graphs that are linkless embeddable but not YΔY-reducible and therefore that there are additional forbidden minors for the YΔY-reducible graphs.<a href="#cite_note-t92-3">[3]</a>

Robertson's apex graph is shown in the figure. It can be obtained by connecting an apex vertex to each of the degree-three vertices of a <a href="Rhombic_dodecahedron" title="Rhombic dodecahedron">rhombic dodecahedron</a>, or by merging two diametrally opposed vertices of a four-dimensional <a href="Hypercube_graph" title="Hypercube graph">hypercube graph</a>. Because the rhombic dodecahedron's graph is planar, Robertson's graph is an apex graph. It is a <a href="Triangle-free_graph" title="Triangle-free graph">triangle-free graph</a> with minimum <a href="Degree_(graph_theory)" title="Degree (graph theory)">degree</a> four, so it cannot be changed by any YΔY-reduction.<a href="#cite_note-t92-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Nearly_planar_graphs">Nearly planar graphs</h2></div>

If a graph is an apex graph, it is not necessarily the case that it has a unique apex. For instance, in the minor-minimal nonplanar graphs K5 and K3,3, any of the vertices can be chosen as the apex. Wagner (<a href="#CITEREFWagner1967">1967</a>, <a href="#CITEREFWagner1970">1970</a>) defined a nearly planar graph to be a nonplanar apex graph with the property that all vertices can be the apex of the graph; thus, K5 and K3,3 are nearly planar. He provided a classification of these graphs into four subsets, one of which consists of the graphs that (like the <a href="M%C3%B6bius_ladder" title="Möbius ladder">Möbius ladders</a>) can be embedded onto the <a href="M%C3%B6bius_strip" title="Möbius strip">Möbius strip</a> in such a way that the single edge of the strip coincides with a <a href="Hamiltonian_cycle" class="mw-redirect" title="Hamiltonian cycle">Hamiltonian cycle</a> of the graph. Prior to the proof of the <a href="Four_color_theorem" title="Four color theorem">four color theorem</a>, he proved that every nearly planar graph can be colored with at most four colors, except for the graphs formed from a <a href="Wheel_graph" title="Wheel graph">wheel graph</a> with an odd outer cycle by replacing the hub vertex with two adjacent vertices, which require five colors. Additionally, he proved that, with a single exception (the eight-vertex <a href="Complement_graph" title="Complement graph">complement graph</a> of the <a href="Cube" title="Cube">cube</a>) every nearly planar graph has an embedding onto the <a href="Projective_plane" title="Projective plane">projective plane</a>.

However, the phrase "nearly planar graph" is highly ambiguous: it has also been used to refer to apex graphs,<a href="#cite_note-18">[18]</a> graphs formed by adding one edge to a planar graph,<a href="#cite_note-19">[19]</a> and graphs formed from a planar embedded graph by replacing a bounded number of faces by "vortexes" of bounded <a href="Pathwidth" title="Pathwidth">pathwidth</a>,<a href="#cite_note-20">[20]</a> as well as for other less precisely-defined sets of graphs.

<div class="mw-heading mw-heading2"><h2 id="Related_graph_classes">Related graph classes</h2></div>

An abstract graph is said to be n-apex if it can be made planar by deleting n or fewer vertices. A 1-apex graph is also said to be apex.

According to <a href="#CITEREFLiptonMackallMattmanPierce2018">Lipton et al. (2018)</a>, a graph is edge-apex if there is some edge in the graph that can be deleted to make the graph planar. A graph is contraction-apex if there is some edge in the graph that can be contracted to make the graph planar.

In general, if X is a class of graphs, an "apex-X" graph is a graph that can be brought into the class X by deleting some one vertex. For example, an apex-<a href="Cograph" title="Cograph">cograph</a> is a graph G that has a vertex v such that G―v is a cograph.

<ul><li><a href="Polyhedral_pyramid" class="mw-redirect" title="Polyhedral pyramid">Polyhedral pyramid</a>, a 4-dimensional polytope whose vertices and edges form an apex graph, with the apex adjacent to every vertex of a <a href="Polyhedral_graph" title="Polyhedral graph">polyhedral graph</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width reflist-columns-2">

<li id="cite_note-linkless-1">^ <a href="#cite_ref-linkless_1-0">a</a> <a href="#cite_ref-linkless_1-1">b</a> <a href="#CITEREFRobertsonSeymourThomas1993b">Robertson, Seymour & Thomas (1993b)</a>.

</li>

<li id="cite_note-rst93-2">^ <a href="#cite_ref-rst93_2-0">a</a> <a href="#cite_ref-rst93_2-1">b</a> <a href="#CITEREFRobertsonSeymourThomas1993a">Robertson, Seymour & Thomas (1993a)</a>.

</li>

<li id="cite_note-t92-3">^ <a href="#cite_ref-t92_3-0">a</a> <a href="#cite_ref-t92_3-1">b</a> <a href="#cite_ref-t92_3-2">c</a> <a href="#cite_ref-t92_3-3">d</a> <a href="#CITEREFTruemper1992">Truemper (1992)</a>.

</li>

<li id="cite_note-local-4">^ <a href="#cite_ref-local_4-0">a</a> <a href="#cite_ref-local_4-1">b</a> <a href="#CITEREFEppstein2000">Eppstein (2000)</a>; <a href="#CITEREFDemaineHajiaghayi2004">Demaine & Hajiaghayi (2004)</a>.

</li>

<li id="cite_note-gi91-5">^ <a href="#cite_ref-gi91_5-0">a</a> <a href="#cite_ref-gi91_5-1">b</a> <a href="#CITEREFGuptaImpagliazzo1991">Gupta & Impagliazzo (1991)</a>.

</li>

<li id="cite_note-FOOTNOTEPierce2014-6"><a href="#cite_ref-FOOTNOTEPierce2014_6-0">^</a> <a href="#CITEREFPierce2014">Pierce (2014)</a>.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <a href="#CITEREFKawarabayashi2009">Kawarabayashi (2009)</a>.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <a href="#CITEREFLewisYannakakis1980">Lewis & Yannakakis (1980)</a>.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation cs2"><a rel="nofollow" class="external text" href="http://www.openproblemgarden.org/op/jorgensens_conjecture">"Jorgensen's Conjecture"</a>, Open Problem Garden, retrieved 2016-11-13</cite>.

</li>

<li id="cite_note-FOOTNOTEKawarabayashiNorineThomasWollan2012-10"><a href="#cite_ref-FOOTNOTEKawarabayashiNorineThomasWollan2012_10-0">^</a> <a href="#CITEREFKawarabayashiNorineThomasWollan2012">Kawarabayashi et al. (2012)</a>.

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <a href="#CITEREFEppstein2000">Eppstein (2000)</a>; <a href="#CITEREFFrickGrohe2001">Frick & Grohe (2001)</a>; <a href="#CITEREFDemaineHajiaghayi2005">Demaine & Hajiaghayi (2005)</a>.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <a href="#CITEREFDemaineHajiaghayiKawarabayashi2009">Demaine, Hajiaghayi & Kawarabayashi (2009)</a>.

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <a href="#CITEREFGrohe2003">Grohe (2003)</a>.

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <a href="#CITEREFMohar2001">Mohar (2001)</a>.

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <a href="#CITEREFChimaniGutwengerMutzelWolf2009">Chimani et al. (2009)</a>.

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <a href="#CITEREFCabelloMohar2010">Cabello & Mohar (2010)</a>.

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <a href="#CITEREFRobertsonSeymourThomas1993c">Robertson, Seymour & Thomas (1993c)</a>.

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <a href="#CITEREFRobertsonSeymourThomas1993c">Robertson, Seymour & Thomas (1993c)</a>; <a href="#CITEREFEppstein2000">Eppstein (2000)</a>.

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <a href="#CITEREFArchdeaconBonnington2004">Archdeacon & Bonnington (2004)</a>.

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <a href="#CITEREFAbrahamGavoille2006">Abraham & Gavoille (2006)</a>.

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin refbegin-columns references-column-width" style="column-width: 30em">

<ul><li><cite id="CITEREFAbrahamGavoille2006" class="citation cs2">Abraham, Ittai; Gavoille, Cyril (2006), "Object location using path separators", <a href="Symposium_on_Principles_of_Distributed_Computing" title="Symposium on Principles of Distributed Computing">Proc. 25th ACM Symposium on Principles of Distributed Computing (PODC '06)</a>, pp. 188–197, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1146381.1146411">10.1145/1146381.1146411</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-59593-384-0</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8844836">8844836</a></cite>.</li>

<li><cite id="CITEREFArchdeaconBonnington2004" class="citation cs2"><a href="Dan_Archdeacon" title="Dan Archdeacon">Archdeacon, Dan</a>; Bonnington, C.P.C. Paul (2004), "Obstructions for embedding cubic graphs on the spindle surface", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory, Series B</a>, 91 (2): 229–252, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jctb.2004.02.001">10.1016/j.jctb.2004.02.001</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2292%2F5158">2292/5158</a></cite>.</li>

<li><cite id="CITEREFCabelloMohar2010" class="citation cs2">Cabello, Sergio; <a href="Bojan_Mohar" title="Bojan Mohar">Mohar, Bojan</a> (2010), "Adding one edge to planar graphs makes crossing number hard", <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120314072225/http://www.fmf.uni-lj.si/~mohar/Reprints/Inprint/BM10_SoCG10_Cabello_crossingNumberHard.pdf">Proc. 26th ACM Symposium on Computational Geometry (SoCG '10)</a> (PDF), pp. 68–76, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1810959.1810972">10.1145/1810959.1810972</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4503-0016-2</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17271180">17271180</a>, archived from <a rel="nofollow" class="external text" href="http://www.fmf.uni-lj.si/~mohar/Reprints/Inprint/BM10_SoCG10_Cabello_crossingNumberHard.pdf">the original</a> (PDF) on 2012-03-14, retrieved 2010-08-02</cite>.</li>

<li><cite id="CITEREFChimaniGutwengerMutzelWolf2009" class="citation cs2">Chimani, Markus; Gutwenger, Carsten; <a href="Petra_Mutzel" title="Petra Mutzel">Mutzel, Petra</a>; Wolf, Christian (2009), "Inserting a vertex into a planar graph", <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=1496812">Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09)</a>, pp. 375–383</cite>.</li>

<li><cite id="CITEREFDemaineHajiaghayi2004" class="citation cs2"><a href="Erik_Demaine" title="Erik Demaine">Demaine, Erik D.</a>; Hajiaghayi, Mohammad Taghi (2004), "Diameter and treewidth in minor-closed graph families, revisited", <a href="Algorithmica" title="Algorithmica">Algorithmica</a>, 40 (3): 211–215, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00453-004-1106-1">10.1007/s00453-004-1106-1</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:390856">390856</a></cite>.</li>

<li><cite id="CITEREFDemaineHajiaghayi2005" class="citation cs2"><a href="Erik_Demaine" title="Erik Demaine">Demaine, Erik D.</a>; Hajiaghayi, Mohammad Taghi (2005), "Bidimensionality: new connections between FPT algorithms and PTASs", <a rel="nofollow" class="external text" href="https://web.archive.org/web/20181211095652/http://erikdemaine.org/papers/GenApprox_SODA2005/">Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA '05)</a>, pp. 590–601, archived from <a rel="nofollow" class="external text" href="http://erikdemaine.org/papers/GenApprox_SODA2005/">the original</a> on 2018-12-11, retrieved 2010-08-02</cite>.</li>

<li><cite id="CITEREFDemaineHajiaghayiKawarabayashi2009" class="citation cs2"><a href="Erik_Demaine" title="Erik Demaine">Demaine, Erik D.</a>; Hajiaghayi, Mohammad Taghi; <a href="Ken-ichi_Kawarabayashi" title="Ken-ichi Kawarabayashi">Kawarabayashi, Ken-ichi</a> (2009), <a rel="nofollow" class="external text" href="http://erikdemaine.org/papers/ApexMinorFree_ICALP2009/paper.pdf">"Approximation algorithms via structural results for apex-minor-free graphs"</a> (PDF), <a href="International_Colloquium_on_Automata%2C_Languages_and_Programming" title="International Colloquium on Automata, Languages and Programming">Proc. 36th International Colloquium Automata, Languages and Programming (ICALP '09)</a>, Lecture Notes in Computer Science, vol. 5555, Springer-Verlag, pp. 316–327, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-02927-1_27">10.1007/978-3-642-02927-1_27</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1721.1%2F62243">1721.1/62243</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-02926-4</bdi></cite>.</li>

<li><cite id="CITEREFEppstein2000" class="citation cs2"><a href="David_Eppstein" title="David Eppstein">Eppstein, David</a> (2000), "Diameter and treewidth in minor-closed graph families", <a href="Algorithmica" title="Algorithmica">Algorithmica</a>, 27 (3): 275–291, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/math.CO/9907126">math.CO/9907126</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs004530010020">10.1007/s004530010020</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3172160">3172160</a></cite>.</li>

<li><cite id="CITEREFFrickGrohe2001" class="citation cs2">Frick, Markus; <a href="Martin_Grohe" title="Martin Grohe">Grohe, Martin</a> (2001), "Deciding first-order properties of locally tree-decomposable structures", <a href="Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a>, 48 (6): 1184–1206, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0004007">cs/0004007</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F504794.504798">10.1145/504794.504798</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:999472">999472</a></cite>.</li>

<li><cite id="CITEREFGrohe2003" class="citation cs2">Grohe, Martin (2003), "Local tree-width, excluded minors, and approximation algorithms", <a href="Combinatorica" title="Combinatorica">Combinatorica</a>, 23 (4): 613–632, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/math.CO/0001128">math.CO/0001128</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00493-003-0037-9">10.1007/s00493-003-0037-9</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11751235">11751235</a></cite>.</li>

<li><cite id="CITEREFGuptaImpagliazzo1991" class="citation cs2">Gupta, A.; <a href="Russell_Impagliazzo" title="Russell Impagliazzo">Impagliazzo, R.</a> (1991), <a rel="nofollow" class="external text" href="http://www.cse.ucsd.edu/users/russell/arvind.ps">"Computing planar intertwines"</a>, <a href="Symposium_on_Foundations_of_Computer_Science" title="Symposium on Foundations of Computer Science">Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91)</a>, IEEE Computer Society, pp. 802–811, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1991.185452">10.1109/SFCS.1991.185452</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8186-2445-0</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:209133">209133</a></cite>.</li>

<li><cite id="CITEREFJørgensen1994" class="citation cs2">Jørgensen, Leif K. (1994), "Contractions to K8", Journal of Graph Theory, 18 (5): 431–448, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fjgt.3190180502">10.1002/jgt.3190180502</a></cite>. As cited by Robertson, Seymour, and Thomas (<a href="#CITEREFRobertsonSeymourThomas1993a">1993a</a>, <a href="#CITEREFRobertsonSeymourThomas1993c">1993c</a>).</li>

<li><cite id="CITEREFKawarabayashi2009" class="citation cs2"><a href="Ken-ichi_Kawarabayashi" title="Ken-ichi Kawarabayashi">Kawarabayashi, Ken-ichi</a> (2009), <a rel="nofollow" class="external text" href="http://research.nii.ac.jp/~k_keniti/focsfinal.pdf">"Planarity allowing few error vertices in linear time"</a> (PDF), <a href="Symposium_on_Foundations_of_Computer_Science" title="Symposium on Foundations of Computer Science">Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS '09)</a>, IEEE Computer Society, pp. 639–648, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FFOCS.2009.45">10.1109/FOCS.2009.45</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4244-5116-6</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11647021">11647021</a></cite>.</li>

<li><cite id="CITEREFKawarabayashiNorineThomasWollan2012" class="citation cs2"><a href="Ken-ichi_Kawarabayashi" title="Ken-ichi Kawarabayashi">Kawarabayashi, Ken-ichi</a>; Norine, Serguei; <a href="Robin_Thomas_(mathematician)" title="Robin Thomas (mathematician)">Thomas, Robin</a>; Wollan, Paul (2012), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{6}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{6}}</annotation>

</semantics>

</math><img src="./f6739d4144330840d9a11aa97b8af44cdf6ae52a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.027ex; height:2.509ex;" alt="{\displaystyle K_{6}}" loading="lazy"> minors in large 6-connected graphs, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1203.2192">1203.2192</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2012arXiv1203.2192K">2012arXiv1203.2192K</a></cite>.</li>

<li><cite id="CITEREFLewisYannakakis1980" class="citation cs2">Lewis, John M.; <a href="Mihalis_Yannakakis" title="Mihalis Yannakakis">Yannakakis, Mihalis</a> (1980), "The node-deletion problem for hereditary properties is NP-complete", <a href="Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a>, 20 (2): 219–230, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2880%2990060-4">10.1016/0022-0000(80)90060-4</a></cite>.</li>

<li><cite id="CITEREFLiptonMackallMattmanPierce2018" class="citation cs2">Lipton, Max; Mackall, Eoin; Mattman, Thomas W.; Pierce, Mike; Robinson, Samantha; Thomas, Jeremy; Weinschelbaum, Ilan (2018), "Six variations on a theme: Almost planar graphs", Involve: A Journal of Mathematics, 11 (3): 413–448, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1608.01973">1608.01973</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2140%2Finvolve.2018.11.413">10.2140/involve.2018.11.413</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:119740613">119740613</a></cite>.</li>

<li><cite id="CITEREFMohar2001" class="citation cs2"><a href="Bojan_Mohar" title="Bojan Mohar">Mohar, Bojan</a> (2001), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170922003345/http://www.fmf.uni-lj.si/~mohar/Papers/ApexGenus.pdf">"Face covers and the genus problem for apex graphs"</a> (PDF), <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory, Series B</a>, 82 (1): 102–117, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjctb.2000.2026">10.1006/jctb.2000.2026</a>, archived from <a rel="nofollow" class="external text" href="http://www.fmf.uni-lj.si/~mohar/Papers/ApexGenus.pdf">the original</a> (PDF) on 2017-09-22, retrieved 2010-08-02</cite>.</li>

<li><cite id="CITEREFPierce2014" class="citation cs2">Pierce, Mike (2014), <a rel="nofollow" class="external text" href="http://tmattman.yourweb.csuchico.edu/mpthesis.pdf">Searching for and classifying the finite set of minor-minimal non-apex graphs</a> (PDF), Honours thesis, California State University, Chico</cite>.</li>

<li><cite id="CITEREFRobertsonSeymourThomas1993a" class="citation cs2"><a href="Neil_Robertson_(mathematician)" title="Neil Robertson (mathematician)">Robertson, Neil</a>; <a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Seymour, Paul</a>; <a href="Robin_Thomas_(mathematician)" title="Robin Thomas (mathematician)">Thomas, Robin</a> (1993a), <a rel="nofollow" class="external text" href="http://people.math.gatech.edu/~thomas/PAP/hadwiger.pdf">"Hadwiger's conjecture for K6-free graphs"</a> (PDF), <a href="Combinatorica" title="Combinatorica">Combinatorica</a>, 13 (3): 279–361, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01202354">10.1007/BF01202354</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9608738">9608738</a></cite>.</li>

<li><cite id="CITEREFRobertsonSeymourThomas1993b" class="citation cs2"><a href="Neil_Robertson_(mathematician)" title="Neil Robertson (mathematician)">Robertson, Neil</a>; <a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Seymour, P. D.</a>; <a href="Robin_Thomas_(mathematician)" title="Robin Thomas (mathematician)">Thomas, Robin</a> (1993b), "Linkless embeddings of graphs in 3-space", <a href="Bulletin_of_the_American_Mathematical_Society" title="Bulletin of the American Mathematical Society">Bulletin of the American Mathematical Society</a>, 28 (1): 84–89, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/9301216">math/9301216</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0273-0979-1993-00335-5">10.1090/S0273-0979-1993-00335-5</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1164063">1164063</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1110662">1110662</a></cite>.</li>

<li><cite id="CITEREFRobertsonSeymourThomas1993c" class="citation cs2"><a href="Neil_Robertson_(mathematician)" title="Neil Robertson (mathematician)">Robertson, Neil</a>; <a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Seymour, Paul</a>; <a href="Robin_Thomas_(mathematician)" title="Robin Thomas (mathematician)">Thomas, Robin</a> (1993c), "A survey of linkless embeddings", in <a href="Neil_Robertson_(mathematician)" title="Neil Robertson (mathematician)">Robertson, Neil</a>; <a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Seymour, Paul</a> (eds.), <a rel="nofollow" class="external text" href="http://people.math.gatech.edu/~thomas/PAP/linklsurvey.pdf">Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors</a> (PDF), Contemporary Mathematics, vol. 147, American Mathematical Society, pp. 125–136</cite>.</li>

<li><cite id="CITEREFTruemper1992" class="citation cs2">Truemper, Klaus (1992), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170829042050/http://www.utdallas.edu/~klaus/Mbook/matroiddecompositionbook.pdf">Matroid Decomposition</a> (PDF), Academic Press, pp. 100–101, archived from <a rel="nofollow" class="external text" href="http://www.utdallas.edu/~klaus/Mbook/matroiddecompositionbook.pdf">the original</a> (PDF) on 2017-08-29, retrieved 2010-08-02</cite>.</li>

<li><cite id="CITEREFWagner1967" class="citation cs2 cs1-prop-foreign-lang-source"><a href="Klaus_Wagner" title="Klaus Wagner">Wagner, Klaus</a> (1967), "Fastplättbare Graphen", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a> (in German), 3 (4): 326–365, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0021-9800%2867%2980103-0">10.1016/S0021-9800(67)80103-0</a></cite>.</li>

<li><cite id="CITEREFWagner1970" class="citation cs2 cs1-prop-foreign-lang-source"><a href="Klaus_Wagner" title="Klaus Wagner">Wagner, Klaus</a> (1970), "Zum basisproblem der nicht in die projektive ebene einbettbaren graphen, I", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a> (in German), 9 (1): 27–43, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0021-9800%2870%2980052-7">10.1016/S0021-9800(70)80052-7</a></cite>.</li></ul>

</div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-02" href="https://en.wikipedia.org/wiki/?title=Apex_graph&oldid=1293525663">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>